//给你一个排序后的字符列表 letters ，列表中只包含小写英文字母。另给出一个目标字母 target，请你寻找在这一有序列表里比目标字母大的最小字母。 
//
// 在比较时，字母是依序循环出现的。举个例子： 
//
// 
// 如果目标字母 target = 'z' 并且字符列表为 letters = ['a', 'b']，则答案返回 'a' 
// 
//
// 
//
// 示例： 
//
// 输入:
//letters = ["c", "f", "j"]
//target = "a"
//输出: "c"
//
//输入:
//letters = ["c", "f", "j"]
//target = "c"
//输出: "f"
//
//输入:
//letters = ["c", "f", "j"]
//target = "d"
//输出: "f"
//
//输入:
//letters = ["c", "f", "j"]
//target = "g"
//输出: "j"
//
//输入:
//letters = ["c", "f", "j"]
//target = "j"
//输出: "c"
//
//输入:
//letters = ["c", "f", "j"]
//target = "k"
//输出: "c"
// 
//
// 
//
// 提示： 
//
// 
// letters长度范围在[2, 10000]区间内。 
// letters 仅由小写字母组成，最少包含两个不同的字母。 
// 目标字母target 是一个小写字母。 
// 
// Related Topics 数组 二分查找 
// 👍 130 👎 0

package com.cute.leetcode.editor.cn;
public class FindSmallestLetterGreaterThanTarget {
    public static void main(String[] args) {
        Solution solution = new FindSmallestLetterGreaterThanTarget().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 1.二分法查找：注意这一题可能存在连续个target，所以在letters[mid] === target的时候进行了额外的判断
         *  如果队列中不存在target的时候，最后一次left==right时会进行判断：
         *      如果当前元素>target的话right会为mid-1，此时right会指向比target大的前一个元素，即比target小的第一个元素
         *      如果当前元素<target的话right还会指向mid，即为比target小的第一个元素
         *      所以以上两种情况在最终返回的时候返回letters[right+1]即可
         *      参考题解之后可以进行优化
         *
         * 2.遍历也行，遍历一圈遇到大的就返回，不然就返回第0个
         */
        public char nextGreatestLetter(char[] letters, char target) {
            if (target > letters[letters.length-1]||target < letters[0]) return letters[0];
            int left = 0;
            int right = letters.length -1;
            int mid;
            /*while (left<=right){
                mid = left + (right -left)/2;
                if (letters[mid]>target) right = mid -1;
                else if (letters[mid]<target) left = mid + 1;
                else{
                   while (mid < letters.length&&letters[mid] == target)mid++;
                   if (mid == letters.length) return letters[0];
                   else return letters[mid];
                }
            }
            return letters[right+1];*/
            while(left + 1 < right){
                // 二分法模板③，l始终在目标字符或者目标字符的左边，r 始终再目标字符的右边，
                // 当两者相遇跳出循环时，r刚好在目标字符位置的右边
                mid = left + (right - left)/2;
                if(letters[mid] > target) right = mid;
                else left = mid;
            }
            return letters[right];

        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}